package BIT;

public class BITTree {
    public int  size;
    public int  tree[];

    public BITTree(int []nums)
    {
        size=nums.length;
        tree=new int[size+1];
        buildTree(nums);
    }

    //初始化
    public void buildTree(int []nums)
    {
        for(int i=1;i<=size;++i)
            update(i,nums[i-1]);
    }

    //单点更新
    public void update(int i,int x)
    {
        for(int j=i;j<=size;j+=lowBit(j))
        {
            tree[j]+=x;
        }
    }

    public int lowBit(int x)
    {
        return x&(-x);
    }

    //区间查询
    public int query(int a,int b)
    {
        return query(b)-query(a-1);
    }

    //查询前缀和
    public int query(int a)
    {
        int ans=0;
        for(int i=a;i>0;i-=lowBit(i))
            ans+=tree[i];
        return ans;
    }
}
